﻿203, 移除链表元素
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL)
    {
        return NULL;
    }

    ListNode* pcur = head;
    ListNode* prev = head;
    while (pcur != NULL)
    {

        if (pcur->val == val)
        {
            if (pcur == head)
            {
                head = head->next;
            }
            else
            {
                prev->next = pcur->next;
            }
            pcur = pcur->next;
        }
        else
        {
            prev = pcur;
            pcur = pcur->next;
        }
    }
    return head;
}

206.反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
    {
        return NULL;
    }

    ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while (n2 != NULL)
    {
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if (n3 != NULL)
        {
            n3 = n3->next;
        }
    }
    return n1;
}

876.链表的中间结点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast, * slow;
    fast = head;
    slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

面试题 02.02.返回倒数第k个结点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (k--)
    {
        fast = fast->next;
    }
    while (fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}


21.合并两个有序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* newhead = NULL;
    if (list1->val < list2->val)
    {
        newhead = list1;
        list1 = list1->next;
    }
    else
    {
        newhead = list2;
        list2 = list2->next;
    }
    struct ListNode* cur = newhead;
    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val)
        {
            cur->next = list1;
            cur = cur->next;
            list1 = list1->next;
        }
        else
        {
            cur->next = list2;
            cur = cur->next;
            list2 = list2->next;
        }
    }
    if (list1 == NULL)
    {
        cur->next = list2;
    }
    if (list2 == NULL)
    {
        cur->next = list1;
    }
    return newhead;
}

CM11.链表分割（牛客）
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* bigtail, * bighead, * smalltail, * smallhead;
        bigtail = bighead = (struct ListNode*)malloc(sizeof(struct ListNode));
        smalltail = smallhead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* pcur = pHead;
        while (pcur != NULL)
        {
            if (pcur->val < x)
            {
                smalltail->next = pcur;
                smalltail = smalltail->next;
            }
            else
            {
                bigtail->next = pcur;
                bigtail = bigtail->next;
            }
            pcur = pcur->next;
        }
        bigtail->next = NULL;
        smalltail->next = bighead->next;
        return smallhead->next;
    }
};

OR36 链表的回文结构（牛客）
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* slow = A;
        struct ListNode* fast = A;
        while (fast != NULL)
        {
            if (fast->next != NULL)
            {
                fast = fast->next->next;
            }
            else
            {
                fast = fast->next;
            }
            slow = slow->next;
        }

        struct ListNode* n1, * n2, * n3;
        n1 = NULL;
        n2 = slow;
        n3 = slow->next;
        while (n2 != NULL)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3 != NULL)
            {
                n3 = n3->next;
            }
        }

        while (n1 != NULL)
        {
            if (A->val != n1->val)
            {
                return false;
            }
            A = A->next;
            n1 = n1->next;
        }
        return true;
    }
};

160.相交链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int countA = 0, countB = 0;
    struct ListNode* tailA = headA, * tailB = headB;
    while (tailA->next)
    {
        countA++;
        tailA = tailA->next;
    }
    while (tailB->next)
    {
        countB++;
        tailB = tailB->next;
    }
    if (tailA != tailB)
    {
        return NULL;
    }
    if (countA > countB)
    {
        int step = countA - countB;
        while (step)
        {
            headA = headA->next;
            step--;
        }
        while (headA)
        {
            if (headA == headB)
            {
                break;
            }
            else
            {
                headA = headA->next;
                headB = headB->next;
            }
        }
    }
    else
    {
        int step = countB - countA;
        while (step)
        {
            headB = headB->next;
            step--;
        }
        while (headB)
        {
            if (headA == headB)
            {
                break;
            }
            else
            {
                headA = headA->next;
                headB = headB->next;
            }
        }
    }
    return headA;
}

141.环形链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    bool hasCycle(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}

142.环形链表II
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            struct ListNode* plist = slow->next;
            slow->next = NULL;
            int count1 = 0, count2 = 0;
            struct ListNode* cur1 = plist;
            struct ListNode* cur2 = head;
            while (cur1)
            {
                cur1 = cur1->next;
                count1++;
            }
            while (cur2)
            {
                cur2 = cur2->next;
                count2++;
            }
            struct ListNode* longs = count1 > count2 ? plist : head;
            struct ListNode* shorts = count1 > count2 ? head : plist;
            int val = fabs(count1 - count2);
            while (val)
            {
                longs = longs->next;
                val--;
            }
            while (longs)
            {
                if (longs == shorts)
                {
                    return longs;
                }
                longs = longs->next;
                shorts = shorts->next;
            }
        }
    }
    return NULL;
}

138.随机链表的复制
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
    struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
    {
        return head;
    }
    //将链表的每一个元素都在其后位置复制一次
    struct Node* cur = head;
    while (cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        newnode->next = cur->next;
        cur->next = newnode;
        cur = newnode->next;
    }

    //复制random
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;

    }

    //将链表拆下来，同时复原原链表
    struct Node* copyhead;
    struct Node* copytail;
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (cur == head)
        {
            copyhead = copy;
            copytail = copy;

        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }
        cur->next = next;
        cur = next;
    }
    return copyhead;
}